package 随意刷;

import java.util.Stack;

/**
 * @Author zhang lei
 * @Date 2021-11-20 13:16
 * 直方图最大矩形面积
 */
public class Offere039 {

    public static void main(String[] args) {
        Offere039 o = new Offere039();
        int[] h = {2,1,5,6,2,3};
        int[] h2 = {2,4};
        System.out.println(o.largestRectangleArea(h));
    }
    public int largestRectangleArea(int[] heights) {
        //分别计算以当前值为最大值的面积
        /**
         * O(n^2)
         */
//        return method1(heights);
        /**
         * 分治法  总共有三种可能， 若下标为index
         * 1. 以全局最低点* length
         * 2. 最大值都在  index 左侧
         * 3. 最大值都在  index 右侧
         */
//        return fenzhi(heights, 0, heights.length);

        /**
         * 单调栈
         */
        return stack(heights);
    }

    private int stack(int[] heights) {
        Stack<Integer> s = new Stack<>();

        //设置一个虚拟高，让后面的都能弹出来
        s.push(-1);
        int maxArea = -1;
        for (int i = 0; i < heights.length; i++) {
            while (s.peek()!=-1 && heights[i]<heights[s.peek()] ) {
                //计算以 s.pop()为高， 左右都比他小的宽
                int height = heights[s.pop()];
                int width = i - s.peek() -1;
                maxArea = Math.max(maxArea, width*height);
            }
            s.push(i);
        }
        while ( s.peek()!=-1) {
            int height = heights[s.pop()];
            int width = heights.length - s.peek() -1;
            maxArea = Math.max(maxArea, width*height);
        }
        return maxArea;
    }

    private int fenzhi(int[] heights, int begin, int end) {
        if(begin == end) {
            return 0;
        }
        if(begin+1 == end) {
            return heights[begin];
        }

        int index = -1;
        int min = Integer.MAX_VALUE;
        for (int i = begin; i < end; i++) {
            if(heights[i]<min) {
                min = heights[i];
                index = i;
            }
        }

        return Math.max(min*(end-begin), Math.max(fenzhi(heights, begin, index), fenzhi(heights, index+1, end)));
    }

    private int method1(int[] heights) {
        int maxArea = -1;
        for (int i = 0; i < heights.length; i++) {
            int min = heights[i];
            for (int j = i; j < heights.length; j++) {
                min = Math.min(min, heights[j]);
                maxArea = Math.max(maxArea, min*(j-i+1));
            }
        }
        return maxArea;
    }

    /**
     * 计算以index为中心的最大面积
     * @param heights
     * @param index
     * @return
     */
    private int getCurMax(int[] heights, int index) {
        int leftIndex = index-1;
        int rightIndex = index +1;

        int leftArea = heights[index];
        int rightArea = heights[index];

        int leftMin = heights[index];
        int rightMin = heights[index];
        while (leftIndex>=0) {
            int left = heights[leftIndex];
            leftMin = Math.min(leftMin, left);
            leftArea = Math.max(leftMin*(index-leftIndex+1), leftArea);
            leftIndex--;
        }
        while (rightIndex<heights.length) {
            int right = heights[rightIndex];
            rightMin = Math.min(right, rightMin);
            rightArea = Math.max(rightArea, (rightIndex-index+1)*rightMin);
            rightIndex++;
        }
        return Math.max(leftArea, rightArea);
    }
}
